package org.lql.algo.codecrush.hot100.linked;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-10-11 15:05
 * @description: 148. 排序链表 <a href="https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class SortList {

	public ListNode sortList(ListNode head) {
		// 递归终止条件
		if (head == null || head.next == null) {
			return head;
		}

		// 1. 使用快慢指针找中点（slow 停在前半部分尾部）
		ListNode slow = head, fast = head.next;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}

		// 2. 拆分链表
		ListNode mid = slow.next;
		slow.next = null;

		// 3. 递归排序左右两部分
		ListNode left = sortList(head);
		ListNode right = sortList(mid);

		// 4. 合并两个有序链表
		return merge(left, right);
	}

	// 合并两个有序链表
	private ListNode merge(ListNode l1, ListNode l2) {
		ListNode dummy = new ListNode(0);
		ListNode cur = dummy;
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				cur.next = l1;
				l1 = l1.next;
			} else {
				cur.next = l2;
				l2 = l2.next;
			}
			cur = cur.next;
		}
		if (l1 != null) cur.next = l1;
		if (l2 != null) cur.next = l2;
		return dummy.next;
	}

	public static void main(String[] args) {
		ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
		ListNode listNode = new SortList().sortList(head);
		while (listNode != null) {
			System.out.print(listNode.val + " -> ");
			listNode = listNode.next;
		}
	}
}
